class Solution {
    /*
        我们定义函数 S(i) ，它的功能是计算以 0（包括 0）开始加到 i（包括 i）的值。

        那么 S(j) - S(i - 1) 就等于 从 i 开始（包括 i）加到 j（包括 j）的值。

        我们进一步分析，实际上我们只需要遍历一次计算出所有的 S(i), 其中 i 等于 0,1,2….,n-1。
        然后我们再减去之前的 S(k),其中 k 等于 0，1，i - 1，中的最小值即可。 因此我们需要
        用一个变量来维护这个最小值，还需要一个变量维护最大值。

        这种算法的时间复杂度 O(N), 空间复杂度为 O(1)。
    */
    public int maxSubArray(int[] nums) {
        int minSum = 0;
        int sum = 0;
        int ans = nums[0];
        for(int i : nums){
            sum += i;     // 前缀和
            ans = Math.max(ans,sum-minSum); // 获取最大值  
            /*
                 为什么更新minSum的操作要在最后一步？
                 因为对于nums.length == 1的数组来说，
            */
            minSum = Math.min(minSum,sum);  // 更新最小的前缀和
            
        }
        return ans;
    }
}
class Solution {
    public int maxSubArray(int[] nums) {
        int nowSum = 0, maxAns = nums[0];
        for(int i : nums){
            /*
             f(i) 代表以第 i个数结尾的「连续子数组的最大和」
            对于第f(i)，我们只要选取f(i-1)+i 和 i  较大的就可以
            */
            nowSum = Math.max(i,nowSum+i);
            maxAns = Math.max(maxAns,nowSum);
        }
        return maxAns;
    }
}
